package stack.easy;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;

/**
 * 1. 问题描述
 *
 * 2， 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 面试题下一个更大元素1 {
    public static void main(String[] args) {
        int[] ans = {1,2,3};
    }


    /**
     * 暴力法 没有利用题目中的任何条件  虽然可以解决问题，但是效率实在太低，不推荐
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len = nums1.length;
        int[] ans = new int[len]; // 记录结果
        for(int i = 0; i < len; i++) {
            // 找出第i个元素在num2中的下一个元素
            int index = 0; // 找到第i个元素在num2中的位置
            while(nums2[index] != nums1[i]) {
                index++;
            }
            // 从index后面找到第一个比num1[i]大的元素
            // 注意如果当前index已经到达最后，说明不存在
            if(index == nums2.length) {
                ans[i] = -1;
            }
            boolean hasexit = false;
            for(int j = index; j < nums2.length; j++) {
                if(nums2[j] > nums1[i]) {
                    hasexit = true;
                    ans[i] = nums2[j];
                    break;
                }
            }
            if(!hasexit) {
                ans[i] = -1;
            }
        }
        return ans;
    }


    /**
     * 使用单调栈求出第二个数组的每个数字的右边第一个比当前元素大的数字
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new ArrayDeque<>(); // 创建栈
        HashMap<Integer,Integer> map = new HashMap<>();
        //  利用单调栈求出数组2中每个元素的右边第一个比它大的数字的值
        for(int i = 0; i < nums2.length; i++) {
            // 维护栈顶元素，当前入栈元素的永远都比栈顶元素小或者等于
            while(!stack.isEmpty() && stack.peek() < nums2[i]) {
                map.put(stack.pop(),nums2[i]);
            }
            stack.push(nums2[i]);
        }
        for(int num2 : nums2) {
            if(!map.containsKey(num2)) {
                map.put(num2,-1);
            }
        }
        int[] ans = new int[nums1.length];
        for(int i = 0; i < nums1.length; i++) {
            ans[i] = map.get(nums1[i]);
        }
        return ans;
    }
}
